package leetcode_ago.bin_tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树的root，确定它是否是一个完全二叉树。
 * 在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的
 * 并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含1到2的h次方个节点之间的最后一级。
 * 分析:完全二叉树中所有节点的编号和满二叉树中节点编号一一对应。
 * 其实完全二叉树就是满二叉树缺了“右下角”而已，完全二叉树中
 * 每一层都尽量排满，若有一层节点没有排满，节点都靠左排列，不可能存在只有右树没有左树的节点
 *思路：可以通过标记位切换两种状态解决
 * 第一状态：二叉树每个节点都有左右子树
 * 切换状态的条件:
 * 1.碰到第一个只有左子树没有右子树的节点时
 * 2.碰到第一个叶子节点时
 * 第二状态：二叉树只有叶子节点
 */
public class Num958_CompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return true;
        }
       //设置标记位
        Boolean marketBit=false;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(!marketBit){
                if(cur.left!=null&&cur.right!=null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else if(cur.left!=null){
                    marketBit=true;
                    queue.offer(cur.left);
                }else if(cur.right!=null){
                    return false;
                }else {
                    marketBit=true;
                }
            }else{
                //此时在第二状态，所有节点都是叶子节点
                if(cur.left!=null||cur.right!=null){
                    return false;
                }
            }
        }
        return true;
    }
}
